/*================================================================
*   文件名称：main.cpp
*   创 建 者：yang qiang
*   创建日期：2019年09月15日
*   版    本：v1.0.0
*   描    述：
*   Copyright (C) 2019 All rights reserved.
*   
* ================================================================*/


#include <iostream>
#include <vector>
#include <stack>
#include <map>

using namespace std;

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */


class Solution {
private:
    vector<int> res;
    map<int, int> datamap;
    int maxtime = 0;

public:
    int findTreeSum(TreeNode* root){
        int leftval = 0, rightval = 0, sum = 0;
        if(root->left)
            leftval = findTreeSum(root->left);
        if(root->right)
            rightval = findTreeSum(root->right);

        sum = leftval + rightval + root->val;
        map<int,int>::iterator it = datamap.find(sum);
        if(it != datamap.end()){
            datamap[sum] = it->second + 1;
        }else{
            datamap[sum] = 1;
        }

        return sum;
    }

    vector<int> findFrequentTreeSum(TreeNode* root) {
        if(root == NULL){
            return res;
        }

        findTreeSum(root);

        map<int,int>::iterator it;
        for(it = datamap.begin(); it != datamap.end(); it++){
            if(it->second > maxtime){
                res.clear();
                res.push_back(it->first);
                maxtime = it->second;           
            }else if(it->second == maxtime){
                res.push_back(it->first);
            }
        }
        
        return res;
    }
};